package leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;


public class RemoveDuplicateLetters {

	public static void main(String[] args) {
		RemoveDuplicateLetters object = new RemoveDuplicateLetters();
		System.out.println(object.removeDuplicateLetters("bcabc"));
	}
	
	
	//贪心策略不对，比如bcabc
	//https://discuss.leetcode.com/topic/31413/easy-to-understand-iterative-java-solution
	//在discuss中看到一个思想跟我这个有点类似的，然后就行相应修正的
	
	//1. find out the last appeared position for each letter(this step is different)
	//2. find out the smallest index from the map in step 1;
	
	//can't understand
	//3.the first letter in the final result must be the smallest letter from index 0 to index 2;
	//4. repeat step 2 to 3 to find out remaining letters.
	
    public String removeDuplicateLetters(String s) {
        if(s == null || s.length() <= 0){
        	return s;
        }
        StringBuilder sb = new StringBuilder();
        int length = s.length();
        //用以存储字符到下标的映射
        HashMap<Character, Integer> map = new HashMap<>(32);
        
        for(int i = 0; i < length; i++){
        	char c = s.charAt(i);
        	Integer index;
        	if( (index = map.get(c)) == null){
        		map.put(c, i);
        	}else{
        		if(index < length - 1 && s.charAt(index + 1) < c){
        			map.put(c, i);
        		}
        	}
        }
        
        
        //map此时存储了所有的不重复字符
        //我们只需要按照下标顺序重新恢复即可
        List<Entry<Character, Integer>> set = new ArrayList<>(map.entrySet());
        
        Collections.sort(set, new Comparator<Entry<Character,Integer>>() {
        	@Override
        	public int compare(Entry<Character, Integer> object1,
        			Entry<Character, Integer> object2) {
        		return object1.getValue() - object2.getValue();
        	}
		});
        
        for(Entry<Character, Integer> entry : set){
        	sb.append(entry.getKey());
//        	System.out.println(entry.getKey() + "  " + entry.getValue());
        }
        return sb.toString();
    }
    
    //a short concise recurcive solution
    //greey stratedy : the greedy choice (i.e., the leftmost letter in the answer) is the smallest s[i]
    //the suffix s[i .. ] contains all the unique letters.
    //大意是说找到答案中满足第一个字符最小并且包含所有字符的s[i]
    
    public String removeDuplicateLetters2(String s) {
        int[] cnt = new int[26];
        int pos = 0; // the position for the smallest s[i]
        for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < s.charAt(pos)) pos = i;
            //使用pos记录了最小的字符，且是最靠左边的
            //如果i出现的次数是1次,那么就break
            if (--cnt[s.charAt(i) - 'a'] == 0) break;
        }
//        After determining the greedy choice s[i], we get a new string s' from s by
//
//        removing all letters to the left of s[i],
//        removing all s[i]'s from s.
        return s.length() == 0 ? "" : s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
    }
}
